#include <iostream>
#include <vector>
using namespace std;

/**
  * @方法: 快速排序, 随机选取基准，期望复杂度为 nlogn
  * @时间复杂度: o(nlogn)
  * @空间复杂度: o(1)
  * @评价:
*/
void quickSort(vector<int>& nums, int left, int right){
    if(left >= right) return;
    int i = left;
    int j = right;
    int id = rand() % (right - left + 1) + left;
    int base = nums[id];
    swap(nums[left], nums[id]);
    while(i < j){
        while(nums[j] > base && j > i) j--;
        while(nums[i] <= base && i < j) i++;
        if(i < j) swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[j]);
    quickSort(nums, left, i-1);
    quickSort(nums, i+1, right);
}


/**
  * @方法: 归并排序
  * @时间复杂度: o(nlogn)
  * @空间复杂度: o()
  * @评价:
*/
vector<int> merge(vector<int>& nums1, vector<int>& nums2){

    vector<int> aa;
    int p = 0;
    int q = 0;
    while(p < nums1.size() && q < nums2.size()){
        if(nums1[p] <= nums2[q]){
            aa.push_back(nums1[p++]);
        }else{
            aa.push_back(nums2[q++]);
        }
    }
    if(p == nums1.size()){
        while(q < nums2.size()) aa.push_back(nums2[q++]);
    }else{
        while(p < nums1.size()) aa.push_back(nums1[p++]);
    }
    return aa;
}
vector<int> mergeSort(vector<int>& nums, int left, int right){
    if(left == right) return vector<int> {nums[left]};
    int mid = left+right >> 1;
    vector<int> n1 = mergeSort(nums, left, mid);
    vector<int> n2 = mergeSort(nums, mid + 1, right);
    return merge(n1, n2);
}


/**
  * @方法: 冒泡排序
  * @时间复杂度: o()
  * @空间复杂度: o()
  * @评价:
*/
void bubble(vector<int>& nums) {
    int n = nums.size();
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);
        }
    }
}


// 测试函数
vector<int> sortArray(vector<int>& nums) {
    // quickSort(nums, 0, nums.size() - 1);
    bubble(nums);
    return nums;
}

int main(){
    cout << "hello world\n";
    vector<int> nums{-4,0,7,4,9,-5,-1,0,-7,-1};
    vector<int> ans = sortArray(nums);
    for(int x:ans){
        cout << x <<", ";
    }
    return 0;
}